/**
 * 快速排序算法，是目前排序最快的算法
 *      算法思想：选取一个值作为枢纽j，然后将 >= 的值放在 枢纽的右侧，小于等于的放在枢纽的左侧
 *              然后对 (0, j - 1) 和 (j + 1, n) 的数据再次进行相同的操作，直到 左侧下标 >= 右侧下标 时退出
 *              使用了 分治递归的思想
 * @param {*} list 需要进行排序的数据
 * @param {*} t 列表左边下标
 * @param {*} w 列表右边下标
 */
function quickSort(list, t, w) {
    
    if (t >= w) return 

    let x, i = t, j = w, z
    
    // 三者取中法
    let m = Math.floor((t + w)/2)
    let e

    if (list[t] > list[m]) {
        e = list[t]
        list[t] = list[m]
        list[m] = e
    }
    if (list[m] > list[w]) {
        e = list[m]
        list[m] = list[w]
        list[w] = e
    }
    if (list[t] > list[m]) {
        e = list[t]
        list[t] = list[m]
        list[m] = e
    }

    e = list[w]
    list[w] = list[m]
    list[m] = e

    x = list[w]
    j--

    console.log(j)

    while (i < j) {
        while ((i < j) && list[i] <= x) {
            i++
        }
        while ((i < j) && list[j] >= x) { 
            j--
        }
        if (i < j) {
            z = list[i]
            list[i] = list[j]
            list[j] = z
            i++
        }
    }

    list[w] = list[j]
    list[j] = x

    quickSort(list, t, j - 1)
    quickSort(list, j + 1, w)

    
    // console.log(list)
}

const data = [5,4,6,2,10,100,58,-1,5,4,6,2,10,100,58,-1]
quickSort(data, 0, data.length - 1)


// /**
//  * 快排，默认选择第一个元素值为 中间点
//  * @param {*} list 
//  * @param {*} t 
//  * @param {*} w 
//  */
// function qSort(list, t, w) {
//     let i, j, k, x
//     if (t >= w) return
//     i = t, j = w, x = list[i]
//     while (i < j) {
//         while ((i < j) && list[j] >= x) j--
//         if (i < j) { 
//             list[i] = list[j]
//             i++
//         }
//         while ((i < j) && list[i] <= x) i++
//         if (i < j) {
//             list[j] = list[i]
//             j--
//         }
//     }
//     list[i] = x
//     qSort(list, t, j - 1)
//     qSort(list, j + 1, w)
//     console.log(list)
// }

// qSort([5,4,6,2,10,100,58,-1], 0, 7)